package LCR_095;

public class Main {
    public static void main(String[] args) {

    }
}

class Solution {
    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace"));
    }
    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for (int k = 0; k <= text1.length(); k++) {
            for (int l = 0; l <= text2.length(); l++) {
                dp[k][l] = -1;
            }
        }
        return f2(text1, 0, text2, 0, dp);
    }
    public static int f2(String text1, int i, String text2, int j, int[][] dp) {
        if(i==text1.length()||j==text2.length()) {
            return 0;
        }
        if(dp[i][j]!=-1) {
            return dp[i][j];
        }
        int ans = 0;
        if(text1.charAt(i)==text2.charAt(j)) {
            ans += f2(text1, i+1, text2, j+1, dp)+1;
        }else {
            int ans1 = f2(text1, i+1, text2, j, dp);
            int ans2 = f2(text1, i, text2, j+1, dp);
            ans += Math.max(ans1, ans2);
        }
        dp[i][j] = ans;
        return ans;
    }
    public static int f1(String text1, int i, String text2, int j) {
        if(i==text1.length()||j==text2.length()) {
            return 0;
        }
        int ans = 0;
        if(text1.charAt(i)==text2.charAt(j)) {
            ans += f1(text1, i+1, text2, j+1)+1;
        }else {
            int ans1 = f1(text1, i+1, text2, j);
            int ans2 = f1(text1, i, text2, j+1);
            ans += Math.max(ans1, ans2);
        }
        return ans;
    }
}
